package org.aplombh.java.leetcode.all;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class _23合并K个升序链表 {
    public static void main(String[] args) {
//        ListNode[] listNodes = new ListNode[2];
        ListNode[] listNodes = new ListNode[1];
//        listNodes[0] = new ListNode(1);
//        listNodes[1] = new ListNode(2);
        System.out.println(new Solution23_1().mergeKLists(listNodes));
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution23_1 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length==0)
            return null;

        ListNode h = new ListNode();
        ListNode p = h;
        PriorityQueue<ListNode> lns = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

        for (ListNode node : lists) {
            if (node!=null)
                lns.add(node);
        }

        while (!lns.isEmpty()) {
            ListNode l = lns.poll();

            int lv = l.val;

            l = l.next;

            if (l != null)
                lns.add(l);

            p.next = new ListNode(lv);
            p = p.next;

        }
        return h.next;
    }
}